package com.leetcode.algorithm.y19.m03;

/**
 * leetcode-cn.com
 * (done)942. 增减字符串匹配
 * (done)999. 车的可用捕获量
 * @author: jie.deng
 * @time: 2019年3月12日 下午11:42:03
 */
public class MySolution0313 {
	
    /**
     * 942. 增减字符串匹配
     * 
     * 给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。
     * 
     * 返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：
     * 
     * 如果 S[i] == "I"，那么 A[i] < A[i+1]
     * 如果 S[i] == "D"，那么 A[i] > A[i+1]
     *  
     * 
     * 示例 1：
     * 
     * 输出："IDID"
     * 输出：[0,4,1,3,2]
     * 示例 2：
     * 
     * 输出："III"
     * 输出：[0,1,2,3]
     * 示例 3：
     * 
     * 输出："DDI"
     * 输出：[3,2,0,1]
     *  
     * 
     * 提示：
     * 
     * 1 <= S.length <= 1000
     * S 只包含字符 "I" 或 "D"。
     * @param S
     * @return
     */
	public int[] diStringMatch(String S) {
		// 解题思路:遍历S，遇见第一个I给0，然后碰到I依次增加；遇见第一个D给最大值，然后依次减少
		int len = S.length();
		int[] ret = new int[len + 1];
		int i = 0;
		int d = len;
		for (int j = 0; j < len; j++) {
			if (S.charAt(j) == 'I') {
				ret[j] = i;
				i++;
			} else if (S.charAt(j) == 'D') {
				ret[j] = d;
				d--;
			}
		}
		ret[len] = i;
		return ret;
	}
	
	/**
	 * 999. 车的可用捕获量
	 * 
      * 在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。
      * 车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。
      * 返回车能够在一次移动中捕获到的卒的数量。
      * 
      * 示例 1：
      * 输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
      * 输出：3
      * 解释：
      * 在本例中，车能够捕获所有的卒。
      * 
      * 示例 2：
      * 输入：[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
      * 输出：0
      * 解释：
      * 象阻止了车捕获任何卒。
      * 
      * 示例 3：
      * 输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
      * 输出：3
      * 解释： 
      * 车可以捕获位置 b5，d6 和 f5 的卒。
      * 
      * 提示：
      * board.length == board[i].length == 8
      * board[i][j] 可以是 'R'，'.'，'B' 或 'p'
      * 只有一个格子上存在 board[i][j] == 'R'
	 * @param board
	 * @return
	 */
	public int numRookCaptures(char[][] board) {
		int cnt = 0;
		// 找车R的索引，即 board[row][col] = 'R'
		int row = 0;
		int col = 0;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if (board[i][j] == 'R') {
					row = i;
					col = j;
					break;
				}
			}
		}
		for (int i = row - 1; i >= 0; i--) {
			if (board[i][col] == '.') {
				continue;
			} else if (board[i][col] == 'B') {
				break;
			} else if (board[i][col] == 'p') {
				cnt++;
				break;
			}
		}
		for (int i = row + 1; i < 8; i++) {
			if (board[i][col] == '.') {
				continue;
			} else if (board[i][col] == 'B') {
				break;
			} else if (board[i][col] == 'p') {
				cnt++;
				break;
			}
		}
		for (int j = col - 1; j >= 0; j--) {
			if (board[row][j] == '.') {
				continue;
			} else if (board[row][j] == 'B') {
				break;
			} else if (board[row][j] == 'p') {
				cnt++;
				break;
			}
		}
		for (int j = col + 1; j < 8; j++) {
			if (board[row][j] == '.') {
				continue;
			} else if (board[row][j] == 'B') {
				break;
			} else if (board[row][j] == 'p') {
				cnt++;
				break;
			}
		}
		return cnt;
	}
}
